
//***************************************************************************
//                              DopTree
//***************************************************************************
//  Copyright (C):
//***************************************************************************
//CVSId: "@(#)$Id: ColDopTree.h,v 1.14 2005/01/10 15:29:28 weller Exp $"
//***************************************************************************


#ifndef ColDopTree_H
#define ColDopTree_H
#if defined(__sgi) || defined(_WIN32)
#pragma once
#endif


//---------------------------------------------------------------------------
//  Includes
//---------------------------------------------------------------------------
#include <climits>

#include <col_import_export.h>
#include <ColGeometry.h>
#include <ColExceptions.h>
#include <ColIntersect.h>							// for MaxNVertices

#ifdef _WIN32
#ifdef max
#undef max
#endif
#ifdef min
#undef min
#endif
#endif

using namespace std;

namespace col {

//---------------------------------------------------------------------------
//  Forward References
//---------------------------------------------------------------------------

struct Data;
struct DopTransform;
struct DopNode;


//---------------------------------------------------------------------------
//  Constants
//---------------------------------------------------------------------------


//***************************************************************************
//  Dop
//***************************************************************************

struct COL_EXPORTIMPORT Dop
{
    /// number of orientations of Dop's (= k)
    static const unsigned int NumOri = 24;

    // This define is only needed for DopTree::init().
#define DOPTREE_NUM_ORI 24

	REAL d[NumOri];

	Dop();
	Dop( const Dop  &source );
	Dop( const Point3 &pnt );
	Dop( const Dop  *source );
	void setValues( REAL val[NumOri] );

	void	operator += ( const Dop &other );
	void	operator += ( const Point3 &pnt );
	void	operator += ( REAL delta );
	void	operator -= ( const Dop &other );
	void	operator  = ( const Point3 &pnt );
	void	operator  = ( const Dop &other );
	void	operator  = ( REAL f );
	REAL& operator [] ( const unsigned int k );
	REAL  operator [] ( const unsigned int k ) const;
	Dop		operator *  ( const DopTransform &tf ) const;
	bool	operator == ( const Dop &other ) const;
	bool	operator != ( const Dop &other ) const;

	REAL max( unsigned int *k = NULL ) const;
	bool overlap( const Dop &other ) const;
	bool isDegenerate( void ) const;
	void extend( REAL delta );

	static unsigned int mostParallelOri( const Vector3 &diag, Vector3 *ori = NULL );
	void print( void ) const;
};

//***************************************************************************
//  ElemDop
//***************************************************************************

struct COL_EXPORTIMPORT ElemDop
{
	Dop d;
	
	// the dereference of these 2 pointers are initialzed outside.
	const ColGeometry *geo;
	const Pnt3Array *points;

	unsigned int pgon[MaxNVertices];			// vertices of enclosed polygon
	unsigned int nvertices;
	unsigned int index;							// index of polygon in the geometry
	Point3 center;								// center of polygon
	Dop cc;										// center projected onto Ori

	bool operator < ( const ElemDop &other ) const;
	bool operator > ( const ElemDop &other ) const;
	bool operator <=( const ElemDop &other ) const;
	bool operator >=( const ElemDop &other ) const;
	void operator = ( const ElemDop &other );
	
	/// create the elemdop
	void set( unsigned int index, const Primitive *prim, const Pnt3Array *points );

	static void setSortIndex( unsigned int index );

	static unsigned int sortindex;

private:
	bool operator ==( const ElemDop &other ) const;
};



//**************************************************************************
// DopTransform
//**************************************************************************

struct COL_EXPORTIMPORT DopTransform
{
	DopTransform();
	DopTransform( const Matrix4 &m );
	DopTransform( const Quat &q );
	void operator =( const Matrix4 &m );
	void operator =( const Quat &q );
	void print( void ) const;

	Dop operator *( const Dop &dop ) const;

	/// The transformation matrix
	Vector3 		c[Dop::NumOri];
	/// The translation of the affine transformation
	REAL			o[Dop::NumOri];
	/// The correspondence between old and new DOP coefficients
	unsigned int	Bb[Dop::NumOri][3];
};



//***************************************************************************
//  DopNode
//***************************************************************************

typedef std::vector<const DopNode*> DopNodeList;

struct COL_EXPORTIMPORT DopNode
{
	DopNode();
	virtual ~DopNode() throw();

	bool check( DopNode &other, Data *data );

	bool check_down( const DopNodeList &other, Data *data, const DopTransform &dt ) const;
	bool check_stay( const DopNodeList &other, Data *data, const Dop &e, const DopTransform &dt ) const;

	/// DOP for this node
	Dop				d;

	/// Child contains pointer to children, or,
	/// if node is a leaf, it contains an index to a polygon.
	DopNode*		child[2];
	
	/// The enclosed polygon; if leaf node = indices into vertex array.

	// the dereference of these 2 pointers are initialzed outside.
	const ColGeometry *geo;
	const Pnt3Array *points;

	unsigned int	pgon[3];
	unsigned int	nvertices;

	/// index of enclosed polygon.
	unsigned int	index;

	// for debugging and research
	void			print( int depth, bool print_dops ) const;
	unsigned int	numFaces( void ) const;

protected:

	static const int MaxPrintRecursions = 80;			// for print()
};



//***************************************************************************
//  DopTree
//***************************************************************************


class COL_EXPORTIMPORT DopTree
{

friend struct Dop;
friend struct DopTransform;

//---------------------------------------------------------------------------
//  Public Instance methods
//---------------------------------------------------------------------------

public:

/*------------------ constructors & destructors ---------------------------*/

	DopTree( );
	DopTree( const ColGeometry *geo, vector<const Pnt3Array *> &points );
	virtual ~DopTree() throw();
	
//---------------------------------------------------------------------------
//  Instance variables
//---------------------------------------------------------------------------

	DopNode m_doptree;

//---------------------------------------------------------------------------
//  Class variables
//---------------------------------------------------------------------------

    /// number of vertices of the prototype DOP, given by Pnt[].
    static const unsigned int NumPnts = 2*Dop::NumOri-4;
	

/*------------------------ collsion check ---------------------------------*/

	bool check( const DopTree &other, Data *data ) const;

/*-------------------------- debugging / statistics -----------------------*/

	void printTree( bool print_dops = false ) const;

//---------------------------------------------------------------------------
//  Public Class methods
//---------------------------------------------------------------------------

	static void init( void );

	static void polyFromHalfspaces( const Vector3 halfspace[Dop::NumOri], const Dop &d,
									Point3 pnt[NumPnts], unsigned int *npnts,
									unsigned int face[Dop::NumOri][Dop::NumOri],
									unsigned int face_nv[Dop::NumOri] );

	static int intersectThreePlanes( const Vector3 &a, REAL da,
									 const Vector3 &b, REAL db,
									 const Vector3 &c, REAL dc,
									 Point3 *q );

	static void printVtx2Ori( void );
	static void printPnt( void );
	static void printOri( void );


protected:

	/// max depth of DOP tree (bug if reached)
	static const unsigned int M_MaxDepth = 500;

	/// set of orientations for DOPs
	static Vector3 m_Ori[Dop::NumOri];

	/// set of vertices of prototype DOP
	static Point3 m_Pnt[NumPnts];

	/// correspondence vertex to ori
	static unsigned int m_Vtx2Ori[NumPnts][3];

//---------------------------------------------------------------------------
//  Private Instance methods
//---------------------------------------------------------------------------

protected:

	void constructHier( const ColGeometry *geo, vector<const Pnt3Array *> &points );

	void constructHier( vector<ElemDop> &elem,
						DopNode *bv, unsigned int depth );
	void assignElem( const ElemDop &elem,
					 vector<ElemDop> &elem1, unsigned int *nelems1, Dop *dop1,
					 vector<ElemDop> &elem2, unsigned int *nelems2, Dop *dop2,
					 unsigned int index );

	// prohibit copy constructor & assignment
	DopTree( const DopTree &source );
	DopTree& operator = ( const DopTree &source );

//---------------------------------------------------------------------------
//  Private Class methods
//---------------------------------------------------------------------------

};

} // namespace col

#endif /* ColDopTree_H */

